Ideally, integrated circuits are routed using a single tool, able to manage both large-scale resource allocation and the complex design rules of the integrated circuit fabrication facility. Often, the tradeoffs made by the developers of a full-chip integrated circuit router lead to problems that the router cannot resolve. In these situations the router terminates leaving unrouted wires or wires that do not meet all of the design rules. Most of the design may have been completed, so it would be advantageous to be able to read in only the portions that are known to have problems and send them to an advanced small-scale router.
The smallest circuit elements of integrated circuits, known as leaf cells, are often constructed manually by layout designers. Productivity could be increased if unrouted or partially routed leaf cells could be sent to an advanced small-scale router for completion, but the polygons of these cells are generally not in the preferred format for the routing tool. The layout designer might have merged all overlapping polygons, for example, or might have drawn wires using 45 degree angles instead of the 90 degree angles preferred by most automated integrated circuit routers. Thus it would be advantageous to be able to read polygons of arbitrary shape and convert them to a representation preferred by an integrated circuit router.
Within an integrated circuit router that performs design rule checks as it constructs the routing, overlaps between polygons on the same layer increase the complexity of the software routines which perform the checks, as there are many distinct ways in which overlaps may occur. It is much simpler to disallow overlaps, either by using a single polygon for each wire or by providing for carefully constrained abutments between individual polygons that together will form a wire.
Even when overlaps are disallowed, the polygons within such a router may be complex, especially near a connection point such as a contact to another layer. Routing paths may approach the connection point from multiple directions, including angles that are odd multiples of 45 degrees, and may be offset from the center line of the connection point. Because efficient design rule checks often rely on constrained data representations such as rectangles, trapezoids, or other quadrilaterals, it is advantageous to convert complex polygon shapes to these data representations.
Polygons in an integrated circuit are not completely arbitrary. Routing polygons in particular tend to have portions that are long and thin with parallel sides, conducting signals from one portion of the integrated circuit to another. This suggests a heuristic of using current flow direction, such as is computed during resistance extraction, to partition the polygon. Sections with parallel sides can quickly be converted to the desired data representation. What remains are width changes, bends, wire ends, and junctions.
An early approach that traces pairs of polygon edges to find straight routing stretches is described in “PANAMAP-1: A Mask Pattern Analysis Program for IC/LSI” by T. Ozaki, J. Yoshida, and M. Kosaka in the Proceedings of the 1980 International Symposium on Circuits and Systems, pp. 1020-1026 and “PANAMAP-B: A Mask Verification System for Bipolar IC” by J. Yoshida, T. Ozaki, and Y. Goto in the Proceedings of the 1981 Design Automation Conference, pp. 690-695. Here the center lines of the straight regions are traced to determine the path length; the width of each region is used to estimate the resistance. Corrections for complex shapes such as bends or junctions are determined experimentally. No methods for using the center lines for automation of routing are described.
A partitioning approach was suggested in “Resistance Extraction from Mask Layout Data,” by Mark Horowitz and Robert Dutton, as printed in IEEE Transactions on Computer-Aided Design, July 1983, pp. 145-150. This paper describes the construction of “break lines” at concave corners of the polygon. The method is used only for resistance extraction; in particular it does not guarantee that the shapes resulting from partitioning will have any particular configuration. The only guarantee is that they will have at most eight sides. This is not suitable for use in a router that uses a data representation comprising a single type of shape such as a quadrilateral.
A polygon partitioning method was described in “REX—A VLSI Parasitic Extraction Tool for Electromigration and Signal Analysis,” by Jerry Hwang, Proceedings of the 1991 Design Automation Conference, pp. 717-722. It also generates shapes with an arbitrary number of sides; FIG. 3 on page 719 shows that it has generated a triangle.
U.S. Pat. No. 6,167,555, “System and Method for Converting Polygon-Based Wires of an Integrated Circuit Design to Path-Based Wires,” also uses the method of converting parallel sides of a polygon to wires. If the polygon shape is irregular, it either discards some geometric information or creates a series of non-quadrilateral shapes, e.g. L or T objects, that are not necessarily connected in a sequence. This makes the shapes unsuitable for direct use within present integrated circuit routers. The algorithm also changes the input data in arbitrary ways to meet its own requirements, e.g. that the centerline for a routing path be on grid.
In view of the need to represent complex polygons in the preferred data structures of integrated circuit routers and the limitations in existing approaches, an alternative approach for importing polygon data into an integrated circuit router is highly desirable.